class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        sort(num.begin(), num.end());
        int n = num.size();
        int ans = num[0] + num[1] + num[2];

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1, k = n - 1; j < k; ++j) {
                while (j < k && num[i] + num[j] + num[k] > target) {
                    --k;
                }
                if (j < k) {
                    int diff = abs(num[i] + num[j] + num[k] - target);
                    if (diff < abs(ans - target)) {
                        ans = num[i] + num[j] + num[k];
                    }
                }
                if (k + 1 < n) {
                    int diff = abs(num[i] + num[j] + num[k + 1] - target);
                    if (diff < abs(ans - target)) {
                        ans = num[i] + num[j] + num[k + 1];
                    }
                }
            }
        }
        return ans;

    }
};
